class  ListNode{
    public int val;
    public  ListNode next;
    public  ListNode(int val){
        this.val=val;
    }
}
public class MyLinkedList {
    public  ListNode head;
    public  void createList(){
        ListNode listNode1=new ListNode(12);
        ListNode listNode2=new ListNode(23);
        ListNode listNode3=new ListNode(34);
        ListNode listNode4=new ListNode(45);
        ListNode listNode5=new ListNode(56);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        this.head=listNode1;
    }
    public void display(){
        ListNode cur=this.head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //从指定头节点开始打印
    public void display2(ListNode newHead){
        ListNode cur=newHead;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //查找是否包含关键字key是否在单链表当中
    public  boolean contains(int key){
        ListNode cur=this.head;
        while(cur!=null){
            if (cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //得到单链表的长度
    public int size(){
        int count=0;
        ListNode cur=this.head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //头插法
    public void addFirst(int data){
        ListNode listNode=new ListNode(data);
        listNode.next=this.head;
        this.head=listNode;
    }
    //尾插法
    public void addLast(int data){
        ListNode listNode=new ListNode(data);
        if (this.head==null){
            this.head=listNode;
        }else{
            ListNode cur=this.head;
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=listNode;
        }
    }
    public  ListNode findIndex(int index){
        ListNode cur=this.head;
        while (index-1!=0){
            cur=cur.next;
            index--;
        }
            return cur;
    }
    //任意位置插入，第一个数据节点为0下标
    public  void addIndex(int index,int data){
        if (index<0||index>size()){
            System.out.println("index位置不合法");
        }
        if (index==0){
            addFirst(data);
            return;
        }
        if (index==size()){
            addLast(data);
            return;
        }
        ListNode cur=findIndex(index);
        ListNode node=new ListNode(data);
        node.next=cur.next;
        cur.next=node;
    }
    //找到要删除关键字的前驱
    public ListNode searchPerv(int key){
        ListNode cur=this.head;
        while(cur.next!=null){
            if (cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }
    //删除第一次出现关键字为key的节点
    public  void remove(int key){
        if (this.head==null){
            System.out.println("单链表为空，不能删除！");
            return;
        }
        if (this.head.val==key){
            this.head=this.head.next;
            return;
        }
        ListNode cur=searchPerv(key);
        if (cur==null){
            System.out.println("没有要删除的节点！");
            return;
        }
        ListNode del=cur.next;
        cur.next=del.next;
    }
    //删除所有值为key的节点
    public ListNode  removeAllKey(int key){
        if (this.head==null) return null;
        ListNode prev=this.head;
        ListNode cur=this.head.next;
        while (cur!=null){
            if (cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if (this.head.val==key){
            this.head=this.head.next;
        }
        return this.head;
    }
    //清空链表
    public void clear(){
        while(this.head!=null){
            ListNode curNext=head.next;
            this.head.next=null;
            this.head=curNext;
        }
    }
    //逆置链表
    public ListNode reverseList(){
        if(this.head==null){
            return null;
        }
        ListNode cur=this.head;
        ListNode prev=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curNext;
        }
        return prev;
    }
    //返回链表的中间结点
    public  ListNode middleNode(ListNode head){
        if (head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    //输入一个链表找到倒数第k个结点
    public ListNode FindKthToTail(int k){
        if (k<=0 || head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(k-1!=0){
           fast=fast.next;
           k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return  slow;
    }
    //合并两个有序的链表
    //将所有小于x的结点排在其余结点之前，且不能改变原来数据的顺序
    public ListNode partition(int x){
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=head;
        while(cur!=null){
            if (cur.val<x){
                if (bs==null){
                    bs=cur;
                    be=cur;
                }else{
                    be.next=cur;
                    be=be.next;
                }
            }else{
                if (as==null){
                    as=cur;
                    ae=cur;
                }else{
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        //预防第一个为空
        if (bs==null){
            return as;
        }
        be.next=as;
        //预防第2个段当中的数据，最后一个节点不是空的
        if(as != null) {
            ae.next = null;
        }
        return bs;
    }
    //在一个排序的链表中，存在重复的结点，删除该链表中重复的结点，重复的结点不保留
    public  ListNode deleteDuplication(){
        ListNode cur=head;
        ListNode newHead=new ListNode(-1);
        ListNode tmp=newHead;
        while(cur!=null){
            if (cur.next!=null&&cur.val==cur.next.val){
                while(cur.next!=null&&cur.val==cur.next.val){
                    cur=cur.next;
                }
                //多走一步
                cur=cur.next;
            }else{
                tmp.next=cur;
                tmp=tmp.next;
                cur=cur.next;
            }
        }
        //防止最后一个结点的值也是重复的
        tmp.next=null;
        return newHead.next;
    }
    //对于一个链表，请设计一个时间复杂度为O（n），额外空间复杂度为O（1）的算法。判断其是否为回文结构
    public boolean chkPalindrome(ListNode A){
        if(head==null){
            return true;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //slow走到了中间位置-->反转
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //反转完成
        while(head!=slow){
            if (head.val!=slow.val){
                return false;
            }
            if (head.next==slow){
                return true;
            }
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
//输入两个链表找出他们的公共结点
    public ListNode getIntersectionNode(ListNode headA,ListNode headB){
       if (headA==null||headB==null){
           return null;
       }
        ListNode pl=headA;
        ListNode ps=headB;

        int lenA=0;
        int lenB=0;
        while(pl!=null){
            lenA++;
            pl=pl.next;
        }
        pl=headA;
        while(ps!=null){
            lenB++;
            ps=ps.next;
        }
        ps=headB;
        int len=lenA-lenB;
        if (len<0){
            pl=headB;
            ps=headA;
            len=lenB-lenA;
        }

        //1.pl永远指向了最长的链表，ps永远指向最短的链表2.求到了差值len步

        //pl走差值len步
        while(len!=0){
            pl=pl.next;
            len--;
        }
        //直到相遇
        while(pl!=ps){
            pl=pl.next;
            ps=ps.next;
        }
        return pl;
    }
    //给定一个链表判断链表是否有环
    public boolean hasCycle(){
        if (head==null)return false;
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow){
                return true;
            }
        }
        return false;
    }
    public boolean hasCycle2(){
        if (head==null)return false;
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow){
               break;
            }
        }
        if (fast==null||fast.next!=null){
            return false;
        }
        return true;
    }
    public void createLoop(){
        ListNode cur=this.head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=head.next.next;
    }
//给定一个链表，返回链表开始如环的第一个结点。如果链表无环，则返回null
public ListNode detectCycle(ListNode head){
    if (head==null)return null;
    ListNode fast=head;
    ListNode slow=head;
    while(fast!=null&&fast.next!=null){
        fast=fast.next.next;
        slow=slow.next;
        if (fast==slow){
            break;
        }
    }
    if (fast==null||fast.next!=null){
        return null;
    }
    fast=head;
    while(fast!=slow){
        fast=fast.next;
        slow=slow.next;
    }
    return fast;
}
//
}






































